Title

Similar Question

Solution Tips

方案一: 前缀和变体

var minStartValue = function(nums) {
    // 其实求的就是前缀和的最小值, 如果最小值小于0, 那么就得加上一个 startValue 使其为正数
	// res 是个正数, 因此默认值为 1
    let res = 1;
    let minPreSum = Number.MAX_SAFE_INTEGER;
    let preSum = 0;
    for (let i = 0; i < nums.length; i++) {
        preSum += nums[i];
        // 小贪心: 只有小于0的才考虑更新 min, 因为正数一定不会比 min 小
        // 简化一下复杂的嵌套
        if (preSum < minPreSum && preSum < 0) {
            minPreSum = preSum;
            res = Math.abs(preSum) + 1;
        }
    }

    return res;
};